#define _CRT_SECURE_NO_WARNINGS 1

//https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        int size = words.size();
        int len = words[0].size();
        int m = size * len;
        unordered_map<string, int> cmp;
        for (auto e : words)
            cmp[e]++;
        int n = s.size();
        for (int i = 0; i < len; i++)
        {
            unordered_map<string, int> win;

            for (int left = i, right = i, count = 0; right + len <= n; right += len)
            {
                string tmp = s.substr(right, len);
                win[tmp]++;
                if (cmp.count(tmp) && win[tmp] <= cmp[tmp])
                    count++;
                if (right - left + 1 > m)
                {
                    tmp = s.substr(left, len);
                    if (cmp.count(tmp) && win[tmp] <= cmp[tmp])
                        count--;
                    win[tmp]--;
                    left += len;
                }
                if (count == size)
                    ret.push_back(left);
            }
        }
        return ret;
    }
};
